package com.coolingme.algo_01_list.copylist;

import java.util.HashMap;
import java.util.Map;

/**
 * 复制带指针的随机链表
 *
 * @author wangyue
 * @date 2020/11/3 14:50
 */
public class CopyLinkedRandomList {

    /**
     * 通过HashMap复制
     *
     * @param head
     * @return
     */
    public static LinkedRandomNode copyWithHashMap(LinkedRandomNode head) {
        if (head == null) {
            return null;
        }
        // key为要原值
        // value为复制的值
        Map<LinkedRandomNode, LinkedRandomNode> map = new HashMap(16);

        LinkedRandomNode newHead = head;
        // 完成随机指针
        while (newHead != null) {
            if (!map.containsKey(newHead)) {
                // 复制node
                LinkedRandomNode node = new LinkedRandomNode(newHead.value + "'");
                // 放入Map中,完成映射
                map.put(newHead, node);
            }
            // 复制随机指针
            if (newHead.random != null) {
                LinkedRandomNode random = newHead.random;
                if (!map.containsKey(random)) {
                    // 复制random
                    LinkedRandomNode copyRandom = new LinkedRandomNode(random.value + "'");
                    // 将random也放入映射中
                    map.put(random, copyRandom);
                }
                // 设置随机指针
                map.get(newHead).random = map.get(random);
            }
            newHead = newHead.next;
        }

        // 完成链表next连接
        newHead = head;
        while (newHead != null) {
            // 获取下一个节点
            LinkedRandomNode next = newHead.next;
            // 根据Map中的映射
            // 获取 当前节点的复制对象   和   下一个节点的复制对象
            // 并创建连接
            map.get(newHead).next = map.get(next);
            // 向后移动一位
            newHead = next;
        }
        // 复制后的头节点
        LinkedRandomNode copyHead = map.get(head);
        return copyHead;
    }

    /**
     * 通过复制节点分割 复制
     *
     * @param head
     * @return
     */
    public static LinkedRandomNode copyInSelf(LinkedRandomNode head) {
        if (head == null) {
            return null;
        }
        // 复制节点
        copyNode(head);
        // 复制随机指针
        copyRandomNode(head);
        // 分割链表
        LinkedRandomNode result = split(head);
        return result;
    }

    public static void copyNode(LinkedRandomNode head) {
        LinkedRandomNode node = head;
        while (node != null) {
            // 复制节点
            LinkedRandomNode copy = new LinkedRandomNode(node.value + "'");
            // 连接到链表中
            copy.next = node.next;
            node.next = copy;
            // node向后移
            node = copy.next;
        }
    }


    public static void copyRandomNode(LinkedRandomNode head) {
        LinkedRandomNode node = head;
        while (node != null && node.next != null) {
            if (node.random != null) {
                // 连接拷贝链表的random
                node.next.random = node.random.next;
            }
            // 向后移动两位
            node = node.next.next;
        }
    }


    public static LinkedRandomNode split(LinkedRandomNode head) {
        System.out.println("All:" + head.toString());
        // 拷贝链表的头，作为返回值
        LinkedRandomNode result = head.next;
        // 作为拷贝链表头的指针
        LinkedRandomNode copy = head.next;
        while (head != null && head.next != null) {
            // 重新连接原链表
            head.next = head.next.next;
            // head向后移
            head = head.next;
            if (copy != null && copy.next != null) {
                // 重新连接拷贝链表
                copy.next = copy.next.next;
                // copy向后移
                copy = copy.next;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        LinkedRandomNode node = new LinkedRandomNode(1);
        LinkedRandomNode node2 = node.setNext(2);
        LinkedRandomNode node3 = node2.setNext(3);
        LinkedRandomNode node4 = node3.setNext(4);
        node.random = node4;
        node3.random = node;

        System.out.println("input: " + node.toString());
        LinkedRandomNode copyNode = copyWithHashMap(node);
        System.out.println("output: " + copyNode.toString());

        System.out.println("---------------------------");
        System.out.println("input: " + node.toString());
        LinkedRandomNode copyNode2 = copyInSelf(node);
        System.out.println("output: " + copyNode2.toString());

    }

}
